package leetcode_401_500;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_464 {
    public static void main(String[] args) {
//        System.out.println(canIWin(4, 5));
//        System.out.println(canIWin(10, 11));
        System.out.println(canIWin(4, 6));
    }

    private static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((maxChoosableInteger * (1 + maxChoosableInteger) >> 1) < desiredTotal) {
            return false;
        }
        return dfs(maxChoosableInteger, desiredTotal, 0, 0, new HashMap<>(16));
    }

    private static boolean dfs(int maxC, int des, int now, int sum, Map<Integer, Boolean> map) {
        Boolean res = map.get(now);
        if (res != null) {
            return res;
        }
        res = false;
        for (int i = 0; i < maxC; i++) {
            if (((now >> i) & 1) == 0) {
                if (i + 1 + sum >= des || (!dfs(maxC, des, now | (1 << i), i + 1 + sum, map))) {
                    res = true;
                    break;
                }
            }
        }
        map.put(now, res);
        return res;
    }
}